import java.util.*;

public class Main {
    // 斐波那契凤尾
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long[] arr = new long[100001];
        arr[1] = 1;
        arr[2] = 2;

        int b = -1;
        for (int i = 3; i <= 100000; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
            if (b == -1 && arr[i] > 1000000) {
                b = i;
            }
            arr[i] = arr[i] % 1000000;
        }
        while (in.hasNextInt()) {
            int n = in.nextInt();
            if (n < b) {
                System.out.println(arr[n]);
            } else {
                System.out.printf("%06d\n", arr[n]);
            }
        }
    }


    // 淘宝网店
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextInt()) {
            int y1 = in.nextInt();
            int m1 = in.nextInt();
            int d1 = in.nextInt();
            int y2 = in.nextInt();
            int m2 = in.nextInt();
            int d2 = in.nextInt();
            if (m1 == 2 && d2 == 29 && !isLeapYear(y2)) {
                System.out.println(27);
                continue;
            }
            int[] date = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
            if (isLeapYear(y1)) {
                date[2] = 29;
            }

            int res = 0;
            while (y1 != y2 || m1 != m2 || d1 != d2) {
                if (d1 < date[m1]) {
                    d1++;
                    if (isPrimeNum(m1)) {
                        res += 1;
                    } else {
                        res += 2;
                    }
                } else {
                    if (m1 < 12) {
                        if (isPrimeNum(m1)) {
                            res += 1;
                        } else {
                            res += 2;
                        }
                        m1++;
                    } else {
                        if (isPrimeNum(m1)) {
                            res += 1;
                        } else {
                            res += 2;
                        }
                        m1 = 1;
                        y1++;
                        if (isLeapYear(y1)) {
                            date[2] = 29;
                        } else {
                            date[2] = 28;
                        }
                    }
                    d1 = 1;
                }
            }
            if (isPrimeNum(m1)) {
                res += 1;
            } else {
                res += 2;
            }
            System.out.println(res);
        }
    }

    private static boolean isPrimeNum(int m) {
        return m == 2 || m == 3 || m == 5 || m == 7 || m == 11;
    }

    private static boolean isLeapYear(int y) {
        return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
    }

}
